public class UsePreorderAndInorderCreateTree {
    //根据一棵树的前序遍历和中序遍历构造二叉树；
    //思路构建：1，前序遍历的遍历顺序是根左右；
    //........2.中序遍历的遍历顺序是左根右；
    //........3.进而利用一个指针依次遍历前序遍历；来确定根；
    //........4.根据中序遍历来找到根，确定跟的左右子树；
    //........5,因为左右子树下面还有可能有子根，应此在中序遍历中根会有所不同，因此定义一个指针指向根，
    // 并且顺着根的变化，根的左右子树范围也会发生变换，依次还需要定义两个头尾下标指针来确定变换后左右子树的范围；进而准确的进行构建二叉树；
    static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }
    public int preIndex;
    public TreeNode buildTree(int[] preOrder,int[] inOrder){
        return buildTreeChild(preOrder,inOrder,0,inOrder.length-1);
    }
    public TreeNode buildTreeChild(int[] preOrder,int[] inOrder,int inBegin,int inEnd){
        if(inBegin>inEnd){
            return null;
        }
        //获取二叉树前序遍历的根结点；
        TreeNode root=new TreeNode(preOrder[preIndex]);
        //获取二叉树根结点在中序遍历的位置；
        int rootIndex=find(inOrder,inBegin,inEnd,preOrder[preIndex]);
        preIndex++;
        root.left=buildTreeChild(preOrder,inOrder,inBegin,rootIndex-1);
        root.right=buildTreeChild(preOrder,inOrder,rootIndex+1,inEnd);
        return root;
    }
    public int find(int[] inOrder,int inBegin,int inEnd,int val){
        for(int i=inBegin;i<=inEnd;i++){
            if(inOrder[i]==val){
                return i;
            }
        }
        return -1;
    }

}
